class Node:
    """
    Node represents a node in a binary tree.

    Attributes:
        value: Value stored in the node.
        left: Left child node.
        right: Right child node.
    """

    def __init__(self, value):
        """
        Initialize a Node with a value and empty left and right child nodes.

        Args:
            value: Value for this node.
        """
        self.value = value
        self.left = None
        self.right = None

    def __repr__(self):
        """
        Returns a string representation of the node.

        Returns:
            String representation of the node.
        """
        return f"Node({self.value})"


class BinaryTree:
    """
    BinaryTree represents a binary tree data structure.

    Attributes:
        root: Root node of the binary tree.
    """

    def __init__(self):
        """
        Initialize an empty binary tree with no root node.
        """
        self.root = None

    def __repr__(self):
        """
        Returns a string representation of the BinaryTree.

        Returns:
            String representation of the BinaryTree.
        """
        return f"BinaryTree(size={self.size()}, height={self.height()}, root={self.root})"

    def __str__(self):
        """
        Returns a string representing the BinaryTree.

        Returns:
            String representing the BinaryTree.
        """
        return self._display()

    def insert(self, value):
        """
        Inserts a node with the given value into the binary tree.

        Args:
            value: Value to be inserted into the binary tree.
        """
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert_recursive(value, self.root)

    def _insert_recursive(self, value, current_node):
        """
        Recursive helper method to insert a node with the given value into the binary tree.

        Args:
            value: Value to be inserted into the binary tree.
            current_node: Current node being visited.
        """
        if value < current_node.value:
            if current_node.left is None:
                current_node.left = Node(value)
            else:
                self._insert_recursive(value, current_node.left)
        else:
            if current_node.right is None:
                current_node.right = Node(value)
            else:
                self._insert_recursive(value, current_node.right)

    def search(self, value):
        """
        Searches for a node with the given value in the binary tree.

        Args:
            value: Value to search for in the binary tree.

        Returns:
            True if the node is found, False otherwise.
        """
        return self._search_recursive(value, self.root)

    def _search_recursive(self, value, current_node):
        """
        Recursive helper method to search for a node with the given value in the binary tree.

        Args:
            value: Value to search for in the binary tree.
            current_node: Current node being visited.

        Returns:
            True if the node is found, False otherwise.
        """
        if current_node is None:
            return False
        if value == current_node.value:
            return True
        elif value < current_node.value:
            return self._search_recursive(value, current_node.left)
        else:
            return self._search_recursive(value, current_node.right)

    def delete(self, value):
        """
        Deletes a node with the given value from the binary tree.

        Args:
            value: Value to be deleted from the binary tree.
        """
        self.root = self._delete_recursive(value, self.root)

    def _delete_recursive(self, value, current_node):
        """
        Recursive helper method to delete a node with the given value from the binary tree.

        Args:
            value: Value to be deleted from the binary tree.
            current_node: Current node being visited.

        Returns:
            The updated root node after deletion.
        """
        if current_node is None:
            return current_node

        if value < current_node.value:
            current_node.left = self._delete_recursive(value, current_node.left)
        elif value > current_node.value:
            current_node.right = self._delete_recursive(value, current_node.right)
        else:
            if current_node.left is None and current_node.right is None:
                current_node = None
            elif current_node.left is None:
                current_node = current_node.right
            elif current_node.right is None:
                current_node = current_node.left
            else:
                min_node = self._find_min(current_node.right)
                current_node.value = min_node.value
                current_node.right = self._delete_recursive(min_node.value, current_node.right)

        return current_node

    def _find_min(self, current_node):
        """
        Finds the minimum node in the binary tree.

        Args:
            current_node: Current node being visited.

        Returns:
            The minimum node.
        """
        while current_node.left is not None:
            current_node = current_node.left
        return current_node

    def size(self):
        """
        Calculates the size (number of nodes) of the binary tree.

        Returns:
            Size of the binary tree.
        """
        return self._size_recursive(self.root)

    def _size_recursive(self, current_node):
        """
        Recursive helper method to calculate the size of the binary tree.

        Args:
            current_node: Current node being visited.

        Returns:
            Size of the subtree rooted at the current node.
        """
        if current_node is None:
            return 0
        return 1 + self._size_recursive(current_node.left) + self._size_recursive(current_node.right)

    def height(self):
        """
        Calculates the height of the binary tree.

        Returns:
            Height of the binary tree.
        """
        return self._height_recursive(self.root)

    def _height_recursive(self, current_node):
        """
        Recursive helper method to calculate the height of the binary tree.

        Args:
            current_node: Current node being visited.

        Returns:
            Height of the subtree rooted at the current node.
        """
        if current_node is None:
            return -1
        return 1 + max(self._height_recursive(current_node.left), self._height_recursive(current_node.right))

    def breadth_first_traversal(self):
        """
        Performs breadth-first traversal of the binary tree.

        Returns:
            List of nodes traversed in breadth-first order.
        """
        if self.root is None:
            return []

        result = []
        queue = [self.root]

        while queue:
            current_node = queue.pop(0)
            result.append(current_node.value)

            if current_node.left:
                queue.append(current_node.left)
            if current_node.right:
                queue.append(current_node.right)

        return result


    def _display(self):
        """
        Returns a string representation of the binary tree.

        Returns:
            String representation of the binary tree.
        """
        if self.root is None:
            return "Empty Binary Tree"

        lines, *_ = self._display_helper(self.root)
        return "\n".join(lines)

    def _display_helper(self, node):
        """
        Helper method to construct the string representation of the binary tree.

        Args:
            node: Current node being visited.

        Returns:
            Lines representing the binary tree, along with the width, height, and middle index.
        """
        if node.right is None and node.left is None:
            line = str(node)
            width = len(line)
            height = 1
            middle = width // 2
            return [line], width, height, middle

        if node.right is None:
            lines, n, p, x = self._display_helper(node.left)
            s = str(node)
            u = len(s)
            first_line = (x + 1) * " " + (n - x - 1) * "_" + s
            second_line = x * " " + "/" + (n - x - 1 + u) * " "
            shifted_lines = [line + u * " " for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2

        if node.left is None:
            lines, n, p, x = self._display_helper(node.right)
            s = str(node)
            u = len(s)
            first_line = s + x * "_" + (n - x) * " "
            second_line = (u + x) * " " + "\\" + (n - x - 1) * " "
            shifted_lines = [u * " " + line for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2

        left, n, p, x = self._display_helper(node.left)
        right, m, q, y = self._display_helper(node.right)
        s = str(node)
        u = len(s)
        first_line = (x + 1) * " " + (n - x - 1) * "_" + s + y * "_" + (m - y) * " "
        second_line = x * " " + "/" + (n - x - 1 + u + y) * " " + "\\" + (m - y - 1) * " "
        if p < q:
            left += [n * " "] * (q - p)
        elif q < p:
            right += [m * " "] * (p - q)
        zipped_lines = zip(left, right)
        lines = [first_line, second_line] + [a + u * " " + b for a, b in zipped_lines]
        return lines, n + m + u, max(p, q) + 2, n + u // 2


if __name__ == "__main__":
    # Create a new binary tree
    binary_tree = BinaryTree()

    # Insert nodes into the binary tree
    binary_tree.insert(5)
    binary_tree.insert(3)
    binary_tree.insert(7)
    binary_tree.insert(2)
    binary_tree.insert(4)
    binary_tree.insert(6)
    binary_tree.insert(8)

    # Print the binary tree structure
    print("Binary Tree Structure:")
    print(binary_tree)
    # Output:
    # Binary Tree Structure:
    #             _______Node(5)_______
    #            /                     \
    #     ___Node(3)___          ___Node(7)___
    #    /             \        /             \
    # Node(2)       Node(4)  Node(6)       Node(8)

    # Perform breadth-first traversal
    breadth_first = binary_tree.breadth_first_traversal()
    print("Breadth-First Traversal:", breadth_first)
    # Output:
    # Breadth-First Traversal: [5, 3, 7, 2, 4, 6, 8]

    # Get the size of the binary tree
    tree_size = binary_tree.size()
    print("Binary Tree Size:", tree_size)
    # Output:
    # Binary Tree Size: 7

    # Get the height of the binary tree
    tree_height = binary_tree.height()
    print("Binary Tree Height:", tree_height)
    # Output:
    # Binary Tree Height: 2

    # Search for a node in the binary tree
    node_to_search = 6
    found = binary_tree.search(node_to_search)
    print(f"Node {node_to_search} Found:", found)
    # Output:
    # Node 6 Found: True

    # Delete a node from the binary tree
    node_to_delete = 4
    binary_tree.delete(node_to_delete)

    # Print the binary tree structure after deletion
    print(f"Binary Tree Structure after deleting node {node_to_delete}:")
    print(binary_tree)
    # Output:
    # Binary Tree Structure after deleting node 4:
    #             _______Node(5)_______
    #            /                    \
    #     ___Node(3)           ___Node(7)___
    #    /                    /             \
    # Node(2)              Node(6)       Node(8)
